 #include<bits/stdc++.h>
 using namespace std;
 
 
 int PartSion1(vector<int>& v,int left,int right)
 {
 	if(left == right)
 		return left;
	//[0,less]  the value < v[right]
 	int less = left - 1;
 	int cur = left;
 	while(cur < right)
 	{
 		if(v[cur] <= v[right])
			::swap(v[++less],v[cur]);
		cur++;
	}
	swap(v[++less],v[cur]);
	return less;
 }
 // left < x  mid == x  right > x
 //return equal(x)

 int* PartSion2(vector<int>& v,int left,int right)
 {
 	if(left == right)
 	{
 		return new int[2]{left,right};	
	}
	//[0,less] <x    [big,right] > x
	int less = left - 1;
	int big = right;
	int cur = left;
	while(cur < big)   //warning : no <= 
	{
		if(v[cur] < v[right])
		{
			::swap(v[cur++],v[++less]);
		}
		else if(v[cur] == v[right]) //注意:这里是v[right] 而不是right  注意别手误
		{
			cur++;
		}
		else //v[cur] > right  
		{
			::swap(v[cur],v[--big]);			
		}
	}
	::swap(v[right],v[big]);
	return new int[2]{less+1,big};
 }
 
 void QucikSort_version1(vector<int>& v,int left,int right)
 {
 	if(left >= right)
 		return ;
 	//warning: ()
 	::swap(v[right],v[ left +  rand() % (right - left + 1) ]);   //rand() % (right - left +1) -->range: [0,right-left]    +left : [left,right]
 	int key = PartSion1(v,left,right);
 	//[left,key-1] key [key+1,right]
 	QucikSort_version1(v,left,key-1);
 	QucikSort_version1(v,key+1,right);
 }
 
void QucikSort_version2(vector<int>& v,int left,int right)
 {
 	if(left >= right)
 		return ;
 	//warning: ()
 	::swap(v[right],v[ left +  rand() % (right - left + 1) ]);   //rand() % (right - left +1) -->range: [0,right-left]    +left : [left,right]
 	int* equal = PartSion2(v,left,right);
 	//[left,equal[0]-1] [equal[0],equal[1]] [equal[1]+1,right]
 	QucikSort_version2(v,left,equal[0]-1);
 	QucikSort_version2(v,equal[1]+1,right);
 }
 
 //hoare
 //no left<=right  e.g. :3 17 4 3   return 3的位置,死循环  
 int Process1(vector<int>& v,int left,int right)
 {
 	int keyi = left;
 	while(left < right)
 	{
 		//left find big  right find small
 		//right start
 		while(left < right && v[right] >= v[keyi])
 			right --;
 		while(left < right && v[left] <= v[keyi])
 			left++;
 		
 		if(left < right)
 			::swap(v[left],v[right]);
	}
	::swap(v[left],v[keyi]);
	return left;
 }
 
//挖坑法 
int Process2(vector<int>& v,int left,int right)
{
	int pivot = left;
	int keyValue = v[left];
	while(left < right)
	{
		//left find big  right find small
 		//right start
		while(left < right && v[right] >= keyValue)
			right --;
		::swap(v[right],v[pivot]);
		pivot = right;
		
		while(left < right && v[left] <= keyValue)
			left++;
		::swap(v[left],v[pivot]);
		pivot = left;
	}
	v[pivot] = keyValue;
	return pivot;
}


void QucikSort_version3(vector<int>& v,int left,int right)
 {
 	if(left >= right)
 		return ;
	int key = Process2(v,left,right);
 	QucikSort_version3(v,left,key-1);
 	QucikSort_version3(v,key+1,right);
 }
 
 
 void Merge(vector<int>& v,vector<int>& tmp,int left,int right)
 {
 	int mid = (left + right) / 2;
 	int begin1 = left,end1 = mid;
 	int begin2 = mid+1,end2 = right;
 	
 	int index = left; //no 0!!!
 	while(begin1 <= end1 &&  begin2 <= end2)
 	{
 		if(v[begin1] <= v[begin2])
		 	tmp[index++] = v[begin1++];
		else 
			tmp[index++] = v[begin2++];
	}
	while(begin1 <= end1)   tmp[index++] = v[begin1++];
	while(begin2 <= end2)	tmp[index++] = v[begin2++];
	
	//Copy
	for(int i = left;i<=right;i++)
		v[i] = tmp[i];
 }
 void _mergeSort(vector<int>& v,vector<int>& tmp,int left,int right)
 {
 	if(left >= right)
 		return ;
 	int mid = (left + right) / 2;
 	_mergeSort(v,tmp,left,mid);
 	_mergeSort(v,tmp,mid+1,right);
 	
 	Merge(v,tmp,left,right); //注意这里传参传的是left 和 right 不是0 和 v.size()-1
 }
 void MergeSort(vector<int>& v)
 {
 	 vector<int> tmp(v.size(),0);
 	_mergeSort(v,tmp,0,v.size()-1);
 }
 
 
 
 void QuickSortNonR(vector<int>& v)
 {
 	int begin = 0;
 	int end = v.size()-1;
 	stack<int> st;
 	st.push(end);
 	st.push(begin);
 	while(!st.empty())
 	{
 		int left = st.top();
 		st.pop();
 		int right = st.top();
 		st.pop();
 		
 		int keyi = Process2(v,left,right);
 		//[left,keyi-1] keyi [keyi+1,right]
 		if(keyi -1 > left)
 		{
 			st.push(keyi-1);
			st.push(left);	
		}
		if(right > keyi+1)
		{
			st.push(right);
			st.push(keyi+1);
		}
	}
 }


  #include"sort.hpp"
 #include<time.h>
 #include<cstdio>
 template<class T>
 void Print(const vector<T>& v)
 {
 	for(auto& x:v)
 		cout << x <<" " ;
 	cout << endl;
 }
 //error example : 18 5 4 0  0   -> 4 0 0 5 18
 int main()
 {
 	srand((unsigned int)time(nullptr));
 	for(int i = 0;i<10;i++)
 	{
 		int n = 20;
	 	vector<int> v(n,0);
	 	for(int i = 0;i<n;i++)
	 		v[i] = rand() % 20;
	 	//Print(v);
	 	vector<int> copy = v;
	 	sort(copy.begin(),copy.end());
	 	QuickSortNonR(v);
//	 	QucikSort_version3(v,0,v.size()-1);
	 	for(int i = 0;i<v.size();i++)
	 	{
	 		if(v[i] != copy[i])
	 		{
		 		cout <<"==================" << endl;
		 		Print(v);
		 		Print(copy);
		 		cout <<"==================" << endl;
		 		break;
			}
		}
	 }
 	
 	return 0;
 }